home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / jcool01.zip / TEST_AVL.C < prev    next >
C/C++ Source or Header  |  1992-08-20  |  25KB  |  599 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. // Updated: JAM 08/19/92 -- modernized template syntax, remove macro hacks
  13.  
  14. #include <cool/String.h>
  15. #include <cool/AVL_Tree.h>
  16. #include <test.h>
  17.  
  18. #include <cool/Binary_Node.C>
  19. #include <cool/Binary_Tree.C>
  20. #include <cool/AVL_Tree.C>
  21.  
  22. void test_int_remove (CoolAVL_Tree<int>&);
  23.  
  24. void test_int_insert () {  
  25.   CoolAVL_Tree<int> b0;
  26.   CoolBinary_Node<int>* n0;
  27.  
  28.   TEST ("b0.put(8)", b0.put(8), TRUE);
  29.   TEST ("b0.count() 1", b0.count(), 1);
  30.   TEST ("b0.tree_depth() 0", b0.tree_depth(), 0);
  31.  
  32.   TEST ("b0.put(4)", b0.put(4), TRUE);
  33.   TEST ("b0.count()", b0.count(), 2);
  34.   TEST ("b0.tree_depth()", b0.tree_depth(), 1);
  35.  
  36.   TEST ("b0.put(10)", b0.put(10), TRUE);
  37.   TEST ("b0.count()", b0.count(), 3);
  38.   TEST ("b0.tree_depth()", b0.tree_depth(), 1);
  39.  
  40.   TEST ("b0.put(2)", b0.put(2), TRUE);
  41.   TEST ("b0.count()", b0.count(), 4);
  42.   TEST ("b0.tree_depth()", b0.tree_depth(), 2);
  43.  
  44.   TEST ("b0.put(6)", b0.put(6), TRUE);
  45.   TEST ("b0.count()", b0.count(), 5);
  46.   TEST ("b0.tree_depth()", b0.tree_depth(), 2);
  47.  
  48.   TEST ("b0.put(5)", b0.put(5), TRUE);
  49.   TEST ("b0.count()", b0.count(), 6);
  50.   TEST ("b0.tree_depth()", b0.tree_depth(), 2);
  51.   TEST ("b0.get_root()->get()",b0.get_root()->get(), 6);
  52.   TEST ("b0.find(4)", b0.find(4), TRUE);
  53.   TEST ("(b0.node() == b0.get_root()->get_ltree())",
  54.          (b0.node() == b0.get_root()->get_ltree()), TRUE);
  55.   TEST ("b0.find(8)", b0.find(8), TRUE);
  56.   TEST ("(b0.node() == b0.get_root()->get_rtree())",
  57.          (b0.node() == b0.get_root()->get_rtree()), TRUE);
  58.   TEST ("b0.find(5)",b0.find(5),TRUE);
  59.   n0 = b0.node();
  60.   TEST ("(n0 == (b0.find(4),b0.node()->get_rtree()))",
  61.          (n0 == (b0.find(4),b0.node()->get_rtree())), TRUE);
  62.  
  63.   TEST ("b0.put(9)", b0.put(9), TRUE);
  64.   TEST ("b0.count()", b0.count(), 7);
  65.   TEST ("b0.tree_depth()", b0.tree_depth(), 2);
  66.   TEST ("b0.find(9)", b0.find(9), TRUE);
  67.   TEST ("(b0.node() == b0.get_root()->get_rtree())",
  68.          (b0.node() == b0.get_root()->get_rtree()), TRUE);
  69.   TEST ("(b0.find(8),b0.node()->is_leaf())",
  70.          (b0.find(8),b0.node()->is_leaf()),TRUE);
  71.   TEST ("(b0.find(10),b0.node()->is_leaf())",
  72.          (b0.find(10),b0.node()->is_leaf()),TRUE);
  73.  
  74.   TEST ("b0.put(1)", b0.put(1), TRUE);
  75.   TEST ("b0.count()", b0.count(), 8);
  76.   TEST ("b0.tree_depth()", b0.tree_depth(), 3);
  77.  
  78.   TEST ("b0.put(0)", b0.put(0), TRUE);
  79.   TEST ("b0.count()", b0.count(), 9);
  80.   TEST ("b0.tree_depth()", b0.tree_depth(), 3);
  81.   TEST ("b0.find(1)",b0.find(1),TRUE);
  82.   n0 = b0.node();
  83.   TEST ("(n0 == (b0.find(4),b0.node()->get_ltree()))",
  84.     (n0 == (b0.find(4),b0.node()->get_ltree())), TRUE);
  85.   TEST ("(b0.find(0),b0.node()->is_leaf())",
  86.          (b0.find(0),b0.node()->is_leaf()),TRUE);
  87.   TEST ("(b0.find(2),b0.node()->is_leaf())",
  88.          (b0.find(2),b0.node()->is_leaf()),TRUE);
  89.   
  90.  
  91.   TEST ("b0.put(11)", b0.put(11), TRUE);
  92.   TEST ("b0.count()", b0.count(), 10);
  93.   TEST ("b0.tree_depth()", b0.tree_depth(), 3);
  94.  
  95.   TEST ("b0.put(12)", b0.put(12), TRUE);
  96.   TEST ("b0.count()", b0.count(), 11);
  97.   TEST ("b0.tree_depth()", b0.tree_depth(), 3);
  98.   TEST ("b0.find(11)",b0.find(11),TRUE);
  99.   n0 = b0.node();
  100.   TEST ("(n0 == (b0.find(9),b0.node()->get_rtree()))",
  101.      (n0 == (b0.find(9),b0.node()->get_rtree())), TRUE);
  102.   TEST ("(b0.find(8),b0.node()->is_leaf())",
  103.          (b0.find(8),b0.node()->is_leaf()),TRUE);
  104.   TEST ("(b0.find(10),b0.node()->is_leaf())",
  105.      (b0.find(10),b0.node()->is_leaf()),TRUE);
  106.   test_int_remove(b0);
  107. }
  108.  
  109. void test_int_remove (CoolAVL_Tree<int>& b0) {
  110.   CoolBinary_Node<int>* n0;
  111.  
  112.   TEST ("b0.remove(12)", b0.remove(12), TRUE);
  113.   TEST ("b0.count()", b0.count(), 10);
  114.   TEST ("b0.tree_depth()", b0.tree_depth(), 3);
  115.  
  116.   TEST ("b0.remove(8)", b0.remove(8), TRUE);
  117.   TEST ("b0.count()", b0.count(), 9);
  118.   TEST ("b0.tree_depth()", b0.tree_depth(), 3);
  119.   TEST ("b0.find(10)",b0.find(10),TRUE);
  120.   n0 = b0.node();
  121.   TEST ("(n0 == (b0.get_root()->get_rtree()))",
  122.      (n0 == (b0.get_root()->get_rtree())), TRUE);
  123.   TEST ("(b0.find(9),b0.node()->is_leaf())",
  124.          (b0.find(9),b0.node()->is_leaf()),TRUE);
  125.   TEST ("(b0.find(11),b0.node()->is_leaf())",
  126.      (b0.find(11),b0.node()->is_leaf()),TRUE);
  127.  
  128.   TEST ("b0.remove(1)", b0.remove(1), TRUE);
  129.   TEST ("b0.count()", b0.count(), 8);
  130.   TEST ("b0.tree_depth()", b0.tree_depth(), 3);
  131.   TEST ("b0.find(0)",b0.find(0),TRUE);
  132.   n0 = b0.node();
  133.   TEST ("(n0 == (b0.find(4),b0.node()->get_ltree()))",
  134.      (n0 == (b0.find(4),b0.node()->get_ltree())), TRUE);
  135.   TEST ("b0.find(2)",b0.find(2),TRUE);
  136.   n0 = b0.node();
  137.   TEST ("(n0 == (b0.find(0),b0.node()->get_rtree()))",
  138.      (n0 == (b0.find(0),b0.node()->get_rtree())), TRUE);
  139.  
  140.  
  141.   TEST ("b0.remove(5)", b0.remove(5), TRUE);
  142.   TEST ("b0.count()", b0.count(), 7);
  143.   TEST ("b0.tree_depth()", b0.tree_depth(), 2);
  144.   TEST ("b0.find(2)",b0.find(2),TRUE);
  145.   n0 = b0.node();
  146.   TEST ("(n0 == (b0.find(6),b0.node()->get_ltree()))",
  147.      (n0 == (b0.find(6),b0.node()->get_ltree())), TRUE);
  148.   TEST ("b0.find(4)",b0.find(4),TRUE);
  149.   n0 = b0.node();
  150.   TEST ("(n0 == (b0.find(2),b0.node()->get_rtree()))",
  151.      (n0 == (b0.find(2),b0.node()->get_rtree())), TRUE);
  152.  
  153.   TEST ("b0.remove(9)", b0.remove(9), TRUE);
  154.   TEST ("b0.count()", b0.count(), 6);
  155.   TEST ("b0.tree_depth()", b0.tree_depth(), 2);
  156.  
  157.   TEST ("b0.remove(6)", b0.remove(6), TRUE);
  158.   TEST ("b0.count()", b0.count(), 5);
  159.   TEST ("b0.tree_depth()", b0.tree_depth(), 2);
  160.   TEST ("b0.get_root()->get()",b0.get_root()->get(), 4);
  161.   TEST ("b0.find(2)",b0.find(2),TRUE);
  162.   n0 = b0.node();
  163.   TEST ("(n0 == (b0.find(4),b0.node()->get_ltree()))",
  164.      (n0 == (b0.find(4),b0.node()->get_ltree())), TRUE);
  165.   TEST ("b0.find(10)",b0.find(10),TRUE);
  166.   n0 = b0.node();
  167.   TEST ("(n0 == (b0.find(4),b0.node()->get_rtree()))",
  168.      (n0 == (b0.find(4),b0.node()->get_rtree())), TRUE);
  169.  
  170.   TEST ("b0.remove(4)", b0.remove(4), TRUE);
  171.   TEST ("b0.count()", b0.count(), 4);
  172.   TEST ("b0.tree_depth()", b0.tree_depth(), 2);
  173.   TEST ("b0.get_root()->get()",b0.get_root()->get(), 2);
  174.   TEST ("b0.find(0)",b0.find(0),TRUE);
  175.   n0 = b0.node();
  176.   TEST ("(n0 == (b0.find(2),b0.node()->get_ltree()))",
  177.      (n0 == (b0.find(2),b0.node()->get_ltree())), TRUE);
  178.  
  179.   TEST ("b0.remove(11)", b0.remove(11), TRUE);
  180.   TEST ("b0.count()", b0.count(), 3);
  181.   TEST ("b0.tree_depth()", b0.tree_depth(), 1);
  182.  
  183.   TEST ("b0.remove(2)", b0.remove(2), TRUE);
  184.   TEST ("b0.count()", b0.count(), 2);
  185.   TEST ("b0.tree_depth()", b0.tree_depth(), 1);
  186.   TEST ("b0.get_root()->get()",b0.get_root()->get(), 0);
  187.   TEST ("b0.find(10)",b0.find(10),TRUE);
  188.   n0 = b0.node();
  189.   TEST ("(n0 == (b0.find(0),b0.node()->get_rtree()))",
  190.      (n0 == (b0.find(0),b0.node()->get_rtree())), TRUE);
  191.  
  192.   TEST ("b0.remove(0)", b0.remove(0), TRUE);
  193.   TEST ("b0.count() 1", b0.count(), 1);
  194.   TEST ("b0.tree_depth() 0", b0.tree_depth(), 0);
  195.   TEST ("b0.get_root()->get()",b0.get_root()->get(), 10);
  196.  
  197.   TEST ("b0.remove(10)", b0.remove(10), TRUE);
  198.   TEST ("b0.count() 1", b0.count(), 0);
  199.   TEST ("b0.tree_depth() 0", b0.tree_depth(), 0);
  200. }
  201.  
  202. void test_int_convert () {
  203.   CoolBinary_Tree<int> bt0;
  204.   bt0.put(1),bt0.put(2),bt0.put(3),bt0.put(4),bt0.put(5),bt0.put(6),bt0.put(7);
  205.   TEST ("bt0.count()",bt0.count(),7);
  206.   TEST ("bt0.tree_depth()",bt0.tree_depth(),6);
  207.   CoolAVL_Tree<int> avl0(bt0);
  208.   TEST ("avl0.count()", avl0.count(), 7);
  209.   TEST ("avl0.tree_depth()", avl0.tree_depth(), 2);
  210.   TEST ("avl0.put(9),avl0.put(8)", (avl0.put(9), avl0.put(8)), TRUE);
  211.   TEST ("avl0.tree_depth()", avl0.tree_depth(), 3);
  212.   TEST ("avl0=bt0,avl.count()", (avl0=bt0, avl0.count()), 7);
  213.   TEST ("avl0.tree_depth()", avl0.tree_depth(), 2);
  214.   TEST ("avl0.put(9),avl0.put(8)", (avl0.put(9), avl0.put(8)), TRUE);
  215.   TEST ("avl0.tree_depth()", avl0.tree_depth(), 3);
  216.   TEST ("avl0.clear(),bo.count()", (avl0.clear(), avl0.count()), 0);
  217. }
  218.  
  219. void test_int () {
  220.   CoolAVL_Tree<int> b0;
  221.   TEST ("CoolAVL_Tree<int> b0", b0.count(), 0);
  222.   TEST ("b0.put(1)", b0.put(1), TRUE);
  223.   TEST ("b0.count()", b0.count(), 1);
  224.   TEST ("b0.find(1)", b0.find(1), TRUE);
  225.   TEST ("b0.value()", b0.value(), 1);
  226.   TEST ("b0.remove()", b0.remove(), TRUE);
  227.   TEST ("b0.count()", b0.count(), 0); 
  228.   TEST ("b0.put(4)", b0.put(4), TRUE);
  229.   TEST ("b0.count()", b0.count(), 1);
  230.   TEST ("b0.tree_depth()", b0.tree_depth(), 0);
  231.   TEST ("b0.put(8)", b0.put(8), TRUE);
  232.   TEST ("b0.count()", b0.count(), 2);
  233.   TEST ("b0.tree_depth()", b0.tree_depth(), 1);
  234.   TEST ("b0.put(3)", b0.put(3), TRUE);
  235.   TEST ("b0.count()", b0.count(), 3);
  236.   TEST ("b0.tree_depth()", b0.tree_depth(), 1);
  237.   TEST ("b0.put(1)", b0.put(1), TRUE);
  238.   TEST ("b0.count()", b0.count(), 4);
  239.   TEST ("b0.tree_depth()", b0.tree_depth(), 2);
  240.   TEST ("b0.put(2)", b0.put(2), TRUE);
  241.   TEST ("b0.count()", b0.count(), 5);
  242.   TEST ("b0.tree_depth()", b0.tree_depth(), 2);
  243.   TEST ("b0.put(6)", b0.put(6), TRUE);
  244.   TEST ("b0.count()", b0.count(), 6);
  245.   TEST ("b0.find(2)", b0.find(2), TRUE);
  246.   TEST ("b0.value()", b0.value(), 2);
  247.   TEST ("b0.reset()", (b0.reset(), 1), 1);
  248.   TEST ("b0.next()", b0.next(), TRUE);
  249.   TEST ("b0.value()", b0.value(), 1);
  250.   TEST ("b0.next()", b0.next(), TRUE);
  251.   TEST ("b0.value()", b0.value(), 2);
  252.   TEST ("b0.next()", b0.next(), TRUE);
  253.   TEST ("b0.value()", b0.value(), 3);
  254.   TEST ("b0.next()", b0.next(), TRUE);
  255.   TEST ("b0.value()", b0.value(), 4);
  256.   TEST ("b0.prev()", b0.prev(), TRUE);
  257.   TEST ("b0.value()", b0.value(), 3);
  258.   TEST ("b0.prev()", b0.prev(), TRUE);
  259.   TEST ("b0.value()", b0.value(), 2);
  260.   TEST ("b0.next()", b0.next(), TRUE);
  261.   TEST ("b0.value()", b0.value(), 3);
  262.   TEST ("b0.next()", b0.next(), TRUE);
  263.   TEST ("b0.value()", b0.value(), 4);
  264.   TEST ("b0.next()", b0.next(), TRUE);
  265.   TEST ("b0.value()", b0.value(), 6);
  266.   TEST ("b0.next()", b0.next(), TRUE);
  267.   TEST ("b0.value()", b0.value(), 8);
  268.   TEST ("b0.count()", b0.count(), 6);
  269.   TEST ("b0.find(99)", b0.find(99), FALSE);
  270.   CoolAVL_Tree<int> b1(b0);
  271.   TEST ("CoolAVL_Tree<int> b1(b0)", b1.count(), 6);
  272.   TEST ("b1.remove(3)", b1.remove(3), TRUE);
  273.   TEST ("b1.count()", b1.count(), 5);
  274.   TEST ("b1.find(3)", b1.find(3), FALSE);
  275.   TEST ("b0.remove(3)", b0.remove(3), TRUE);
  276.   TEST ("b0.count()", b0.count(), 5);
  277.   TEST ("b0.find(3)", b0.find(3), FALSE);
  278.   TEST ("b0.put(-3)", b0.put(-3), TRUE);
  279.   TEST ("b0.tree_depth()", b0.tree_depth(), 2);
  280.   TEST ("b0.count()", b0.count(), 6);
  281.   TEST ("b0.put(18)", b0.put(18), TRUE);
  282.   TEST ("b0.tree_depth()", b0.tree_depth(), 2);
  283.   TEST ("b0.count()", b0.count(), 7);
  284.   TEST ("b0.put(13)", b0.put(13), TRUE);
  285.   TEST ("b0.tree_depth()", b0.tree_depth(), 3);
  286.   TEST ("b0.count()", b0.count(), 8);
  287.   TEST ("b0.put(1)", b0.put(1), FALSE);
  288.   TEST ("b0.tree_depth()", b0.tree_depth(), 3);
  289.   TEST ("b0.count()", b0.count(), 8);
  290.   TEST ("b0.put(5)", b0.put(5), TRUE);
  291.   TEST ("b0.tree_depth()", b0.tree_depth(), 3);
  292.   TEST ("b0.count()", b0.count(), 9);
  293.   TEST ("b0.put(17)", b0.put(17), TRUE);
  294.   TEST ("b0.tree_depth()", b0.tree_depth(), 3);
  295.   TEST ("b0.count()", b0.count(), 10);
  296.   TEST ("b0.put(3)", b0.put(3), TRUE);
  297.   TEST ("b0.tree_depth()", b0.tree_depth(), 3);
  298.   TEST ("b0.count()", b0.count(), 11);
  299.   TEST ("b0.find(3)", b0.find(3), TRUE);
  300.   TEST ("b0.find(8)", b0.find(8), TRUE);
  301.   TEST ("b0.find(9)", b0.find(9), FALSE);
  302.   TEST ("b0.find(-3)", b0.find(-3), TRUE);
  303.   TEST ("b0.find(17)", b0.find(17), TRUE);
  304.   TEST ("b1=b0", (b1=b0, b0.count() == b1.count()), 1);
  305.   TEST ("b1.tree_depth()", b1.tree_depth(), 3);
  306.   TEST ("b1.find(3)", b1.find(3), TRUE);
  307.   TEST ("b1.find(8)", b1.find(8), TRUE);
  308.   TEST ("b1.find(9)", b1.find(9), FALSE);
  309.   TEST ("b1.find(-3)", b1.find(-3), TRUE);
  310.   TEST ("b1.find(17)", b1.find(17), TRUE);
  311.   TEST ("b1.put(-4)", b1.put(-4), TRUE);
  312.   TEST ("b1.tree_depth()", b1.tree_depth(), 3);
  313.   TEST ("b1.count()", b1.count(), 12);
  314.   TEST ("b1.put(-5)", b1.put(-5), TRUE);
  315.   TEST ("b1.tree_depth()", b1.tree_depth(), 3);
  316.   TEST ("b1.count()", b1.count(), 13);
  317.   TEST ("b1.put(-6)", b1.put(-6), TRUE);
  318.   TEST ("b1.tree_depth()", b1.tree_depth(), 4);
  319.   TEST ("b1.count()", b1.count(), 14);
  320.   TEST ("b1.put(27)", b1.put(27), TRUE);
  321.   TEST ("b1.tree_depth()", b1.tree_depth(), 4);
  322.   TEST ("b1.count()", b1.count(), 15);
  323.   TEST ("b1.put(7)", b1.put(7), TRUE);
  324.   TEST ("b1.tree_depth()", b1.tree_depth(), 4);
  325.   TEST ("b1.count()", b1.count(), 16);
  326. }  
  327.  
  328.  
  329. typedef char* charP;
  330. int my_comp (const charP& s1, const charP& s2) {
  331.   return strcmp (s1, s2);
  332. }
  333.  
  334. void test_charP () {  
  335.   CoolAVL_Tree<char*> s0;
  336.   TEST ("CoolAVL_Tree<char*> s0", s0.count(), 0);
  337.   TEST ("s0.set_compare(&my_comp)",(s0.set_compare(&my_comp),1),1);
  338.   TEST ("s0.put(\"aaa\")", s0.put("aaa"), TRUE);
  339.   TEST ("s0.count()", s0.count(), 1);
  340.   TEST ("s0.find(\"aaa\")", s0.find("aaa"), TRUE);
  341.   TEST ("s0.value()", (strcmp (s0.value(), "aaa")), 0);
  342.   TEST ("s0.remove()", s0.remove(), TRUE);
  343.   TEST ("s0.count()", s0.count(), 0);
  344.   TEST ("s0.put(\"ddd\")", s0.put("ddd"), TRUE);
  345.   TEST ("s0.count()", s0.count(), 1);
  346.   TEST ("s0.tree_depth()", s0.tree_depth(), 0);
  347.   TEST ("s0.put(\"hhh\")", s0.put("hhh"), TRUE);
  348.   TEST ("s0.count()", s0.count(), 2);
  349.   TEST ("s0.tree_depth()", s0.tree_depth(), 1);
  350.   TEST ("s0.put(\"ccc\")", s0.put("ccc"), TRUE);
  351.   TEST ("s0.count()", s0.count(), 3);
  352.   TEST ("s0.tree_depth()", s0.tree_depth(), 1);
  353.   TEST ("s0.put(\"aaa\")", s0.put("aaa"), TRUE);
  354.   TEST ("s0.count()", s0.count(), 4);
  355.   TEST ("s0.tree_depth()", s0.tree_depth(), 2);
  356.   TEST ("s0.put(\"bbb\")", s0.put("bbb"), TRUE);
  357.   TEST ("s0.count()", s0.count(), 5);
  358.   TEST ("s0.tree_depth()", s0.tree_depth(), 2);
  359.   TEST ("s0.put(\"fff\")", s0.put("fff"), TRUE);
  360.   TEST ("s0.count()", s0.count(), 6);
  361.   TEST ("s0.find(\"bbb\")", s0.find("bbb"), TRUE);
  362.   TEST ("s0.value()", (strcmp (s0.value(), "bbb")), 0);
  363.   TEST ("s0.reset()", (s0.reset(), 1), 1);
  364.   TEST ("s0.next()", s0.next(), TRUE);
  365.   TEST ("s0.value()", (strcmp (s0.value(), "aaa")), 0);
  366.   TEST ("s0.next()", s0.next(), TRUE);
  367.   TEST ("s0.value()", (strcmp (s0.value(), "bbb")), 0);
  368.   TEST ("s0.next()", s0.next(), TRUE);
  369.   TEST ("s0.value()", (strcmp (s0.value(), "ccc")), 0);
  370.   TEST ("s0.next()", s0.next(), TRUE);
  371.   TEST ("s0.value()", (strcmp (s0.value(), "ddd")), 0);
  372.   TEST ("s0.prev()", s0.prev(), TRUE);
  373.   TEST ("s0.value()", (strcmp (s0.value(), "ccc")), 0);
  374.   TEST ("s0.prev()", s0.prev(), TRUE);
  375.   TEST ("s0.value()", (strcmp (s0.value(), "bbb")), 0);
  376.   TEST ("s0.next()", s0.next(), TRUE);
  377.   TEST ("s0.value()", (strcmp (s0.value(), "ccc")), 0);
  378.   TEST ("s0.next()", s0.next(), TRUE);
  379.   TEST ("s0.value()", (strcmp (s0.value(), "ddd")), 0);
  380.   TEST ("s0.next()", s0.next(), TRUE);
  381.   TEST ("s0.value()", (strcmp (s0.value(), "fff")), 0);
  382.   TEST ("s0.next()", s0.next(), TRUE);
  383.   TEST ("s0.value()", (strcmp (s0.value(), "hhh")), 0);
  384.   TEST ("s0.count()", s0.count(), 6);
  385.   TEST ("s0.find(\"ABCD\")", s0.find("ABCD"), FALSE);
  386.   CoolAVL_Tree<char*> s1(s0);
  387.   TEST ("CoolAVL_Tree<char*> s1(s0)", s1.count(), 6);
  388.   TEST ("s1.remove(\"ccc\")", s1.remove("ccc"), TRUE);
  389.   TEST ("s1.count()", s1.count(), 5);
  390.   TEST ("s1.find(\"ccc\")", s1.find("ccc"), FALSE);
  391.   TEST ("s0.remove(\"ccc\")", s0.remove("ccc"), TRUE);
  392.   TEST ("s0.count()", s0.count(), 5);
  393.   TEST ("s0.find(\"ccc\")", s0.find("ccc"), FALSE);
  394.   TEST ("s0.put(\"XXX\")", s0.put("XXX"), TRUE);
  395.   TEST ("s0.tree_depth()", s0.tree_depth(), 2);
  396.   TEST ("s0.count()", s0.count(), 6);
  397.   TEST ("s0.put(\"rrr\")", s0.put("rrr"), TRUE);
  398.   TEST ("s0.tree_depth()", s0.tree_depth(), 2);
  399.   TEST ("s0.count()", s0.count(), 7);
  400.   TEST ("s0.put(\"mmm\")", s0.put("mmm"), TRUE);
  401.   TEST ("s0.tree_depth()", s0.tree_depth(), 3);
  402.   TEST ("s0.count()", s0.count(), 8);
  403.   TEST ("s0.put(\"aaa\")", s0.put("aaa"), FALSE);
  404.   TEST ("s0.tree_depth()", s0.tree_depth(), 3);
  405.   TEST ("s0.count()", s0.count(), 8);
  406.   TEST ("s0.put(\"eee\")", s0.put("eee"), TRUE);
  407.   TEST ("s0.tree_depth()", s0.tree_depth(), 3);
  408.   TEST ("s0.count()", s0.count(), 9);
  409.   TEST ("s0.put(\"qqq\")", s0.put("qqq"), TRUE);
  410.   TEST ("s0.tree_depth()", s0.tree_depth(), 3);
  411.   TEST ("s0.count()", s0.count(), 10);
  412.   TEST ("s0.put(\"ccc\")", s0.put("ccc"), TRUE);
  413.   TEST ("s0.tree_depth()", s0.tree_depth(), 3);
  414.   TEST ("s0.count()", s0.count(), 11);
  415.   TEST ("s0.find(\"ccc\")", s0.find("ccc"), TRUE);
  416.   TEST ("s0.find(\"hhh\")", s0.find("hhh"), TRUE);
  417.   TEST ("s0.find(\"iii\")", s0.find("iii"), FALSE);
  418.   TEST ("s0.find(\"XXX\")", s0.find("XXX"), TRUE);
  419.   TEST ("s0.find(\"qqq\")", s0.find("qqq"), TRUE);
  420.   TEST ("s1=s0", (s1=s0, s0.count() == s1.count()), 1);
  421.   TEST ("s1.tree_depth()", s1.tree_depth(), 3);
  422.   TEST ("s1.find(\"ccc\")", s1.find("ccc"), TRUE);
  423.   TEST ("s1.find(\"hhh\")", s1.find("hhh"), TRUE);
  424.   TEST ("s1.find(\"iii\")", s1.find("iii"), FALSE);
  425.   TEST ("s1.find(\"XXX\")", s1.find("XXX"), TRUE);
  426.   TEST ("s1.find(\"qqq\")", s1.find("qqq"), TRUE);
  427.   TEST ("s1.put(\"WWW\")", s1.put("WWW"), TRUE);
  428.   TEST ("s1.tree_depth()", s1.tree_depth(), 3);
  429.   TEST ("s1.count()", s1.count(), 12);
  430.   TEST ("s1.put(\"VVV\")", s1.put("VVV"), TRUE);
  431.   TEST ("s1.tree_depth()", s1.tree_depth(), 3);
  432.   TEST ("s1.count()", s1.count(), 13);
  433.   TEST ("s1.put(\"UUU\")", s1.put("UUU"), TRUE);
  434.   TEST ("s1.tree_depth()", s1.tree_depth(), 4);
  435.   TEST ("s1.count()", s1.count(), 14);
  436.   TEST ("s1.put(\"zzz\")", s1.put("zzz"), TRUE);
  437.   TEST ("s1.tree_depth()", s1.tree_depth(), 4);
  438.   TEST ("s1.count()", s1.count(), 15);
  439.   TEST ("s1.put(\"ggg\")", s1.put("ggg"), TRUE);
  440.   TEST ("s1.tree_depth()", s1.tree_depth(), 4);
  441.   TEST ("s1.count()", s1.count(), 16);
  442. }  
  443.  
  444. void test_String_2 (CoolAVL_Tree<CoolString>& s0) {
  445.   CoolAVL_Tree<CoolString> s1(s0);
  446.   TEST ("CoolAVL_Tree<CoolString> s1(s0)", s1.count(), 6);
  447.   TEST ("s1.remove(CoolString(\"ccc\"))", s1.remove(CoolString("ccc")), TRUE);
  448.   TEST ("s1.count()", s1.count(), 5);
  449.   TEST ("s1.find(CoolString(\"ccc\"))", s1.find(CoolString("ccc")), FALSE);
  450.   TEST ("s0.remove(CoolString(\"ccc\"))", s0.remove(CoolString("ccc")), TRUE);
  451.   TEST ("s0.count()", s0.count(), 5);
  452.   TEST ("s0.find(CoolString(\"ccc\"))", s0.find(CoolString("ccc")), FALSE);
  453.   TEST ("s0.put(CoolString(\"XXX\"))", s0.put(CoolString("XXX")), TRUE);
  454.   TEST ("s0.tree_depth()", s0.tree_depth(), 2);
  455.   TEST ("s0.count()", s0.count(), 6);
  456.   TEST ("s0.put(CoolString(\"rrr\"))", s0.put(CoolString("rrr")), TRUE);
  457.   TEST ("s0.tree_depth()", s0.tree_depth(), 2);
  458.   TEST ("s0.count()", s0.count(), 7);
  459.   TEST ("s0.put(CoolString(\"mmm\"))", s0.put(CoolString("mmm")), TRUE);
  460.   TEST ("s0.tree_depth()", s0.tree_depth(), 3);
  461.   TEST ("s0.count()", s0.count(), 8);
  462.   TEST ("s0.put(CoolString(\"aaa\"))", s0.put(CoolString("aaa")), FALSE);
  463.   TEST ("s0.tree_depth()", s0.tree_depth(), 3);
  464.   TEST ("s0.count()", s0.count(), 8);
  465.   TEST ("s0.put(CoolString(\"eee\"))", s0.put(CoolString("eee")), TRUE);
  466.   TEST ("s0.tree_depth()", s0.tree_depth(), 3);
  467.   TEST ("s0.count()", s0.count(), 9);
  468.   TEST ("s0.put(CoolString(\"qqq\"))", s0.put(CoolString("qqq")), TRUE);
  469.   TEST ("s0.tree_depth()", s0.tree_depth(), 3);
  470.   TEST ("s0.count()", s0.count(), 10);
  471.   TEST ("s0.put(CoolString(\"ccc\"))", s0.put(CoolString("ccc")), TRUE);
  472.   TEST ("s0.tree_depth()", s0.tree_depth(), 3);
  473.   TEST ("s0.count()", s0.count(), 11);
  474.   TEST ("s0.find(CoolString(\"ccc\"))", s0.find(CoolString("ccc")), TRUE);
  475.   TEST ("s0.find(CoolString(\"hhh\"))", s0.find(CoolString("hhh")), TRUE);
  476.   TEST ("s0.find(CoolString(\"iii\"))", s0.find(CoolString("iii")), FALSE);
  477.   TEST ("s0.find(CoolString(\"XXX\"))", s0.find(CoolString("XXX")), TRUE);
  478.   TEST ("s0.find(CoolString(\"qqq\"))", s0.find(CoolString("qqq")), TRUE);
  479.   TEST ("s1=s0", (s1=s0, s0.count() == s1.count()), 1);
  480.   TEST ("s1.tree_depth()", s1.tree_depth(), 3);
  481.   TEST ("s1.find(CoolString(\"ccc\"))", s1.find(CoolString("ccc")), TRUE);
  482.   TEST ("s1.find(CoolString(\"hhh\"))", s1.find(CoolString("hhh")), TRUE);
  483.   TEST ("s1.find(CoolString(\"iii\"))", s1.find(CoolString("iii")), FALSE);
  484.   TEST ("s1.find(CoolString(\"XXX\"))", s1.find(CoolString("XXX")), TRUE);
  485.   TEST ("s1.find(CoolString(\"qqq\"))", s1.find(CoolString("qqq")), TRUE);
  486.   TEST ("s1.put(CoolString(\"WWW\"))", s1.put(CoolString("WWW")), TRUE);
  487.   TEST ("s1.tree_depth()", s1.tree_depth(), 3);
  488.   TEST ("s1.count()", s1.count(), 12);
  489.   TEST ("s1.put(CoolString(\"VVV\"))", s1.put(CoolString("VVV")), TRUE);
  490.   TEST ("s1.tree_depth()", s1.tree_depth(), 3);
  491.   TEST ("s1.count()", s1.count(), 13);
  492.   TEST ("s1.put(CoolString(\"UUU\"))", s1.put(CoolString("UUU")), TRUE);
  493.   TEST ("s1.tree_depth()", s1.tree_depth(), 4);
  494.   TEST ("s1.count()", s1.count(), 14);
  495.   TEST ("s1.put(CoolString(\"zzz\"))", s1.put(CoolString("zzz")), TRUE);
  496.   TEST ("s1.tree_depth()", s1.tree_depth(), 4);
  497.   TEST ("s1.count()", s1.count(), 15);
  498.   TEST ("s1.put(CoolString(\"ggg\"))", s1.put(CoolString("ggg")), TRUE);
  499.   TEST ("s1.tree_depth()", s1.tree_depth(), 4);
  500.   TEST ("s1.count()", s1.count(), 16);
  501. }  
  502.  
  503. int my_strcmp (const CoolString& s1, const CoolString& s2) {
  504.   return strcmp (s1, s2);
  505. }
  506.  
  507. void test_String () {
  508.   CoolAVL_Tree<CoolString> s0;
  509.   TEST ("CoolAVL_Tree<CoolString> s0", s0.count(), 0);
  510.   TEST ("s0.set_compare(&my_strcmp)",(s0.set_compare(&my_strcmp),1),1);
  511.   TEST ("s0.put(CoolString(\"aaa\"))", s0.put(CoolString("aaa")), TRUE);
  512.   TEST ("s0.count()", s0.count(), 1);
  513.   TEST ("s0.find(CoolString(\"aaa\"))", s0.find(CoolString("aaa")), TRUE);
  514.   TEST ("s0.value()", (strcmp (s0.value(), "aaa")), 0);
  515.   TEST ("s0.remove()", s0.remove(), TRUE);
  516.   TEST ("s0.count()", s0.count(), 0);
  517.   TEST ("s0.put(CoolString(\"ddd\"))", s0.put(CoolString("ddd")), TRUE);
  518.   TEST ("s0.count()", s0.count(), 1);
  519.   TEST ("s0.tree_depth()", s0.tree_depth(), 0);
  520.   TEST ("s0.put(CoolString(\"hhh\"))", s0.put(CoolString("hhh")), TRUE);
  521.   TEST ("s0.count()", s0.count(), 2);
  522.   TEST ("s0.tree_depth()", s0.tree_depth(), 1);
  523.   TEST ("s0.put(CoolString(\"ccc\"))", s0.put(CoolString("ccc")), TRUE);
  524.   TEST ("s0.count()", s0.count(), 3);
  525.   TEST ("s0.tree_depth()", s0.tree_depth(), 1);
  526.   TEST ("s0.put(CoolString(\"aaa\"))", s0.put(CoolString("aaa")), TRUE);
  527.   TEST ("s0.count()", s0.count(), 4);
  528.   TEST ("s0.tree_depth()", s0.tree_depth(), 2);
  529.   TEST ("s0.put(CoolString(\"bbb\"))", s0.put(CoolString("bbb")), TRUE);
  530.   TEST ("s0.count()", s0.count(), 5);
  531.   TEST ("s0.tree_depth()", s0.tree_depth(), 2);
  532.   TEST ("s0.put(CoolString(\"fff\"))", s0.put(CoolString("fff")), TRUE);
  533.   TEST ("s0.count()", s0.count(), 6);
  534.   TEST ("s0.find(CoolString(\"bbb\"))", s0.find(CoolString("bbb")), TRUE);
  535.   TEST ("s0.value()", (strcmp (s0.value(), "bbb")), 0);
  536.   TEST ("s0.reset()", (s0.reset(), 1), 1);
  537.   TEST ("s0.next()", s0.next(), TRUE);
  538.   TEST ("s0.value()", (strcmp (s0.value(), "aaa")), 0);
  539.   TEST ("s0.next()", s0.next(), TRUE);
  540.   TEST ("s0.value()", (strcmp (s0.value(), "bbb")), 0);
  541.   TEST ("s0.next()", s0.next(), TRUE);
  542.   TEST ("s0.value()", (strcmp (s0.value(), "ccc")), 0);
  543.   TEST ("s0.next()", s0.next(), TRUE);
  544.   TEST ("s0.value()", (strcmp (s0.value(), "ddd")), 0);
  545.   TEST ("s0.prev()", s0.prev(), TRUE);
  546.   TEST ("s0.value()", (strcmp (s0.value(), "ccc")), 0);
  547.   TEST ("s0.prev()", s0.prev(), TRUE);
  548.   TEST ("s0.value()", (strcmp (s0.value(), "bbb")), 0);
  549.   TEST ("s0.next()", s0.next(), TRUE);
  550.   TEST ("s0.value()", (strcmp (s0.value(), "ccc")), 0);
  551.   TEST ("s0.next()", s0.next(), TRUE);
  552.   TEST ("s0.value()", (strcmp (s0.value(), "ddd")), 0);
  553.   TEST ("s0.next()", s0.next(), TRUE);
  554.   TEST ("s0.value()", (strcmp (s0.value(), "fff")), 0);
  555.   TEST ("s0.next()", s0.next(), TRUE);
  556.   TEST ("s0.value()", (strcmp (s0.value(), "hhh")), 0);
  557.   TEST ("s0.count()", s0.count(), 6);
  558.   TEST ("s0.find(CoolString(\"ABCD\"))", s0.find(CoolString("ABCD")), FALSE);
  559.   test_String_2 (s0);
  560. }
  561.  
  562. void test_equal (void) {
  563.   CoolAVL_Tree<int> b0, b1;
  564.   for (int i = 0; i < 10; i++) {
  565.     b0.put (i);
  566.     b1.put (i);
  567.   }
  568.   TEST ("b0 == b1", b0 == b1, TRUE);
  569.   b0.put (11);
  570.   TEST ("b0 != b1", b0 != b1, TRUE);
  571. }
  572.  
  573. void test_leak () {
  574.   for (;;) {
  575.     test_int_insert();
  576.     test_int_convert();
  577.     test_int();
  578.     test_charP();
  579.     test_String();
  580.     test_equal();
  581.   }
  582. }
  583.  
  584.  
  585. int main () {
  586.   START("CoolAVL_Tree");
  587.   test_int_insert();
  588.   test_int_convert();
  589.   test_int();
  590.   test_charP();
  591.   test_String();
  592.   test_equal();
  593. #if LEAK
  594.   test_leak();
  595. #endif
  596.   SUMMARY();
  597.   return 0;
  598. }
  599.